class Solution {

    static class TreeNode{
        public int val;
        public TreeNode left; //存储左孩子的引用
        public TreeNode right; //存储右孩子的引用

        public TreeNode(int val){
            this.val = val;
        }
    }

    /** Oj ------  105. 从前序与中序遍历序列构造二叉树
     * 给定两个整数数组preorder和inorder，其中preorder是二叉树的先序遍历，inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。
     */
    public int preIndex = 0; //遍历前序数组的变量
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChile(preorder, inorder, 0, preorder.length-1);
    }

    private TreeNode buildTreeChile(int[] preorder, int[] inorder, int inbegin, int inend) {
        //判断当前的根节点是否还有左子树和右子树
        if(inbegin > inend) { //因为后边一直在递归，所以这个判断条件放在最前边
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        //找到root在中序遍历的位置（下标）
        int rootIndex = findIndex(inorder, inbegin, inend, root.val);
        preIndex++; //找到之后，前序的preIndex变量++，找下一个根节点在中序的位置
        if(rootIndex == -1){
            return null;
        }

        //构建左子树和右子树
        root.left = buildTreeChile(preorder, inorder, inbegin, rootIndex-1);
        root.right = buildTreeChile(preorder, inorder, rootIndex+1, inend);
        return root; 
    }

    private int findIndex(int[] inorder, int inbegin, int inend, int val){
        for(int i = inbegin; i <= inend; i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1; //没找到
    }


    /** Oj -------- 106. 从中序与后序遍历序列构造二叉树
     *给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历，
     * postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。
     */
    public int postIndex = 0; //遍历后序数组的变量
    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        postIndex = postorder.length - 1; //根节点在后序的倒数第一个，所以是postorder.length - 1
        return buildTreeChile2(postorder, inorder, 0, postorder.length-1);
    }

    private TreeNode buildTreeChile2(int[] postorder, int[] inorder, int inbegin, int inend) {
        //判断当前的根节点是否还有左子树和右子树
        if(inbegin > inend) { //因为后边一直在递归，所以这个判断条件放在最前边
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex]);
        //找到root在中序遍历的位置（下标）
        int rootIndex = findIndex2(inorder, inbegin, inend, root.val);
        postIndex--; //找到之后，后序的preIndex变量--，找下一个根节点在中序的位置
        if(rootIndex == -1){
            return null;
        }

        //构建左子树和右子树，后序倒数的节点--都是原右子树的根节点
        root.right = buildTreeChile2(postorder, inorder, rootIndex+1, inend);
        root.left = buildTreeChile2(postorder, inorder, inbegin, rootIndex-1);
        return root;
    }

    private int findIndex2(int[] inorder, int inbegin, int inend, int val){
        for(int i = inbegin; i <= inend; i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1; //没找到
    }

    /** Oj ----------  606. 根据二叉树创建字符串
     * 给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
     * 空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
     */
    public String tree2str(TreeNode root) {
        StringBuilder stringBuilder = new StringBuilder();
        tree2strChild(root, stringBuilder);
        return stringBuilder.toString();
    }
    private void tree2strChild(TreeNode root, StringBuilder stringBuilder) {
        if(root == null) {
            return;
        }
        stringBuilder.append(root.val);
        if(root.left != null){
            stringBuilder.append("(");
            tree2strChild(root.left, stringBuilder);
            stringBuilder.append(")");
        }else{
            if(root.right == null){
                return;
            } else {
                stringBuilder.append("()");
            }
        }
        if(root.right == null){
            return;
        }else{
            stringBuilder.append("(");
            tree2strChild(root.right, stringBuilder);
            stringBuilder.append(")");
        }
    }
}